The present invention relates generally to a method and apparatus for replacing the heap implementation in an existing executable computer program at runtime. In particular, the present invention relates to a method for replacing the heap implementation for the purpose of detecting errors in the use of heap memory in the program. Most particularly, this purpose is to detect memory overwrites, frees of unallocated pointers, writes to free memory, reads of unallocated or uninitialized memory, and memory leaks; and to detect these errors with minimal impact on the runtime speed of the program.
Memory errors have been a major source of software quality problems for decades, but as the complexity of software increases, these errors have become much more difficult to track down. There are several reasons for this difficulty.
First, the symptoms of memory errors are often far removed from their cause. This follows from the nature of the heap: unrelated data are stored in adjacent memory locations within the heap, so reading or writing outside the bounds of a heap object can very easily corrupt unrelated data. Likewise, reading or writing to previously freed memory can corrupt unrelated data since the heap manager may have recycled the freed memory for use elsewhere in the program.
Second, heap errors are hard to reproduce. This also follows from the dynamic nature of the heap: the allocation pattern varies from one run to the next, so different items of program data will be adjacent in memory at each run. Errors in the use of heap memory thus cause corruption of different data in each run, or, in many cases, cause no apparent symptoms if the error happens to corrupt a location in the heap that is not currently in use. This problem is compounded in multi-threaded programs, because even if program inputs are identical from one run to the next, the operating system thread scheduler will schedule threads differently, causing a different allocation pattern. Similarly, in complex client-server programs, it often is not possible to duplicate program input since inputs are concurrently arriving from many different computers.
Finally, heap errors are hard to diagnose even if they can be reproduced. The reason is that traditional development tools such as compilers and source debuggers do not have any knowledge of the heap. If a pointer error occurs, these tools do not provide information about whether the pointer was allocated from the heap, and if so what the size of the heap object is and where and when it was allocated or freed.
A number of solutions to the problem of detecting and diagnosing memory errors exist in the prior art. However, these solutions each have at least two of the following problems: 1) they require special builds of the program that are very time consuming to produce and introduce the risk of testing a different program from the one that is shipped; 2) they cause the program's runtime speed to slow very significantly, making usage on a regular basis impractical; 3) they require modification of or recompilation of the program's source code; or 4) they fail to identity a significant portion of memory errors that exist in a program.
Representative examples of prior art include the following:
Malloc Wrapper Method
In the "malloc wrapper" method, used by BoundsChecker from NuMega Technologies, Inc., heap function calls are intercepted in order to introduce checking code before and/or after the normal heap routines gain control, as illustrated by FIG. 1b. The executable 20 patched with the malloc-wrapper method contains a call 21 to the heap function malloc. At the definition of malloc 22, control transfers at transfer point 23 to the entry portion of a malloc intercept definition 24. The intercept definition returns at location 25 to the original malloc definition at transfer point 23. When the malloc definition returns at its conclusion 26, control passes to a malloc exit intercept definition 27 which returns at its conclusion 28 to the site following the call to malloc at return point 29. This method places guards at the ends of newly-allocated blocks and checks the guards during heap function calls. FIG. 2b shows control-flow when the malloc-wrapper method performs checking. The executable 50 contains a call to malloc and a reference of the allocated memory. During the call to malloc at location 51 checking occurs in the intercept definition 52, then control returns at location 53 to the original executable code.
The malloc-wrapper method suffers from performance degradation on order O(n.sup.2), where n is the number of blocks in the heap, because it checks the entire heap space for overwrites during each heap function call. Validation of heap pointer parameters is also slow since this method must search its own data structures to determine if a pointer points to valid heap memory--it cannot directly validate the heap data structure since it does not implement the heap. Not implementing the heap also causes this method to fail to identify a number of errors. It does not identify corruption of the heap's own data structures, nor does it detect most instances of reads and writes of free memory or double-frees, since the underlying heap manager immediately recycles free memory to satisfy subsequent allocation requests.
Object Code Insertion Method
In the "object code insertion" ("OCI") method, used by Purify from Pure Software, Inc., checking instructions are inserted in the program's object files, between instructions that reference memory, to monitor the program's memory reads and writes, as illustrated by FIG. 2c. The executable 60 contains a call to malloc and a reference of the allocated memory. After the call to malloc and before the following memory-reference instruction, at transfer point 61, control transfers to the checking function 62, then returns at its conclusion 63 to the original executable. This method also uses a malloc wrapper, shown in FIG. 1b, described above, to monitor the program's memory allocations and frees.
The OCI method requires a special build of the program, in which checking instructions are inserted between the program's normal instructions. The OCI method also suffers from performance degradation on the order of between 5.times. and 24.times.. The reason will be apparent to those skilled in the art: performing a function call and looking up data structures during every memory-reference instruction in a program will necessarily have a severe impact on performance. This method was originally implemented on RISC architectures, where performance degradation is on the order 5.times. to 10.times.. On CISC architectures, the performance impact is even more severe due to the number of instructions that can reference memory. Moreover, this method performs function calls and data structure references in between a program's normal instructions, which results in poor locality and few cache hits on modern CPU architectures that utilize on-chip caches; the result is further performance degradation.
Compile Time Instrumentation Method
The "compile time instrumentation" ("CTI") method, used by Insure from Parasoft Corporation, is very similar to the OCI method, except that checking statements are inserted into source code rather than into object code. This method suffers from even more severe performance degradation than the OCI method, but additionally suffers from the need to recompile the program's source code. Portions of the program for which source code is not available, such as system, compiler, and third-party libraries, cannot be checked with this method.
Summary of Prior Art
All the prior art methods for detecting memory errors suffer from severe performance degradation, particularly when the program heap size is large. Most prior art methods also fail to operate on standard builds of programs--they require special builds and/or recompiles of source code. As a result of special build and performance degradation, the program developer or tester is discouraged from using any of these prior art methods on a frequent basis.
Because of the difficulty of reproducing and diagnosing memory errors--a problem that increases with program size and complexity--it is desirable to have memory error checking active at all times during program development and testing. This allows such errors to be detected and diagnosed as soon as possible after the errors are introduced. Likewise, because memory errors sometimes do not show up until a program is subject to live inputs in production, it is desirable to have memory error checking active in deployed business-critical programs, so that the problems can be fixed before critical data becomes corrupted.
Due to the performance degradation they cause, none of the prior art methods of detecting memory errors are suitable for use at all times during program development and testing. And such performance degradation is certainly unacceptable in a deployed setting. It is this need that the present invention addresses.